package randomthoughts.dp;

/**
 * @author tongchen
 * @create 2023-04-19 9:40
 */
public class StealHouseIII {
    public static void main(String[] args) {

    }
    //思路：相对于数组形式dp，树形dp可以采用递归的方式，而采用哪种方式是与我们递推公式有关，如果偷当前结点，那么我的两个子节点就不能偷，

    /**如果不偷当前节点，那我们就选择左右节点偷和不偷的最优解（最大值）
     * 五部曲：1.dp[i]代表当前结点偷还是不偷的最大值 0 不偷 1 偷 2.递推公式max(value+left[0]+right[0],max(left[0],left[1])+max(right[0],right[1]))
     * 3.初始化：在获取值之前，都将其初始化为0即可 4.遍历顺序:后序递归遍历
     * @param cur
     * @return
     */
    public static int[] steal(TreeNode cur){
        //递归检验
        if(cur==null){
            return new int[2];
        }
        int[]left=steal(cur.left);
        int[]right=steal(cur.right);
        int[]res=new int[2];
        res[1]=cur.value+left[0]+right[0];
        res[0]=Math.max(left[1],left[0])+Math.max(right[0],right[1]);
        return res;

    }
}
class TreeNode{
    TreeNode left;
    TreeNode right;
    int value;

}